educationfandomcom-20200222-history
Příklady paralelním architekturám a modelům
=Body: 1= Common CRCW a Arbitrary CRCW. Ktery je silnejsi a proc? Řešení Arbitrary je silnější než Common, protože algoritmy, které předpokládají, že počítač dovolí zapsat jen pokud jsou všechny hodnoty stejné (jinak končí v nedefinovaném stavu -> programátor nesmí dovolit aby došlo k zápisu do jedné buňky sdílené paměti pokud různé hodnoty) tak ve stejném čase a bez jakékoli změny budou tyto algoritmy fungovat na systému který zapíše náhodně vybranou hodnotu. Opačně to fungovat nebude a kdybychom chtěli spustit algoritmus napsaný pro Arbitrary na Common, museli bychom již provádět simulaci silnějšího na slabším. =Bodů: 2= Výpočet pořadí od konce v zřetězeném seznamu na CREW Zadání Popište časově optimální paralelní algoritmus pro výpočet pořadí od konce (rank) prvků ve zřetězeném seznamu o velikosti n na počítači CREW PRAM s n procesory. Vstupem algoritmu je zřetězený seznam ve sdílené paměti PRAM reprezentován pomocí pole následníků S\dots ,n . Řešení Přeskok ukazatelů, viz. slajd =Bodů: 3= PRAM post order cislovani stromu Zadání: *napsat (optimální?) algoritmus * p < n, T(n,p) Řešení pokud ho máš, tak sem s ním! PRAM, procesory s nezavislou pam a arit. jednotkou Zadání Popsat APRAM NC alg. pro paralel. prefix. soucet n cisel pomoci binarni asociativni operace *, T, C a psicka? Řešení pokud ho máš, tak sem s ním! Simulace Prioritni-CRCW na EREW Zadání Popiste a vysvetlete polylogaritmicky slozitou simulaci jednoho kroku Prioritni-CRCW-PRAM(n,p) algoritmu S na EREW-PRAM(n+O(p),) pocitaci. Predpokladejte jednotkovy casovy model, kdy R, W a L trvaji cas 1. Řešení viz slajdy 20-26. Algoritmus vypoctu hloubky uzlu na EREW PRAM Zadání Popiste EREW PRAM alg. pro vypocet hloubky uzlu eulerovskeho stromu T o n uzlech, kdy koren ma hloubku 0. Vysledkem bude pole Level1,...,n. Eulerovsky strom T ma m = 2n-2 hran a je reprezentovan polem uzlu, ktere maji odkazy na cyklicke seznamy svych hran. Predpokladejte, ze jiz je zkonstruovana eulerovska cesta vznikla pri pruchodu T do hloubky a je ulozena v poli EA1,...,m, kde EAi je i-ta hrana teto cesty. Odvodte paralelni cas T(n,p), jestlize lokalni operace L i globalni R/W trvaji cas 1. Řešení pokud ho máš, tak sem s ním! =Bodů: 4= urcete p' a t' u PRAMu (m,p') Zadání Odvodte pocet procesoru p‘ a casovou slozitost t‘ simulace PRAM(n,p) algoritmu s casem t = T(n,p) na PRAM (m,p‘) pocitaci tehoz typu, je-li m < n. Tuto simulaci popiste. Jake dalsi predpoklady jsou treba? Uvazujte jednotkovy casovy model, kdy operace R,W a L trvaji cas 1. Řešení pokud ho máš, tak sem s ním! Určení pořadí v řetězeném seznamu pro PRAM Zadání alg. pro urceni poradi v zretezenem seznamu pro EREW-PRAM s p=n, jakou ma skalovatelnost? napiste alg. pro p=1 krat za sebou jdouci R/W trva k+d-1; a barierova synchronizace B(p)=\alpha d \log{p} , kde \alpha a d > 1) ma nezavislou pametovou a vypocetni jednotku. Popiste cenove optimalni APRAM alg. pro paralelni redukci n cisel pomoci binarni asociativni operace @ (puntik ;-). Odvodte T(n,p), C(n,p), \psi _1(p) , \psi _2(n) . Analyzu casove slozitosti provedte pro model dynamicke barierove synchronizace. Řešení pokud ho máš, tak sem s ním! Provest PPS na APRAM Zadání Melo to byt pro p < n procesoru, takze vlastni vypocet slozitosti mel sekvencni a paralelni cast. Ta paralelni pak vypadala \langle RRLBWB\rangle ^{\log{p}} . Z toho zjistit T(n,p) dosazenim za R,L,W,B, vypocitat C(n,p), Psi1, Psi2. Poznámka APRAM pocitac postupuje stejne jako PRAM pocitac, akorat se musi prokladat barierama Category:Czech Technical University in Prague